#pragma once
#include<vector>
#include<bitset>
#include<iostream>
using namespace std;

namespace ns_bitset {
template<size_t N>
class bitset {
public:
	bitset() {
		_bits.resize((N>>5) + 1);
	}

	void set(size_t x) {
		int i = x / 32;
		int j = x % 32;
		_bits[i] |= (1 << j);
	}

	void reset(size_t x) {
		int i = x / 32;
		int j = x % 32;
		_bits[i] &= ~(1 << j);
	}
	bool check(size_t x) {
		int i = x / 32;
		int j = x % 32;
		return _bits[i] &(1 << j);
	}
	int count() {
		int ret = 0;
		for (auto e : _bits) {
			while (e) {
				e &= e - 1;
				ret++;
			}
		}
		return ret;
	}
private:
	vector<int> _bits;
};

template<size_t N>
class twobitset{
public:
	void set(size_t x) {
		// 00 01 10 11
		if (!bits1.check(x) && !bits2.check(x)) {
			bits2.set(x);
		}
		else if (!bits1.check(x) && bits2.check(x)) {
			bits1.set(x);
			bits2.reset(x);
		}
		else if (bits1.check(x) && !bits2.check(x)) {
			bits2.set(x);
		}
	}
	void Debug() {
		for (size_t i = 0; i < N; i++)
		{
			if (!bits1.check(i)  && bits2.check(i))
			{
				cout << "1->" << i << endl;
			}
			else if (bits1.check(i)  &&!bits2.check(i) )
			{
				cout << "2->" << i << endl;
			}
			else  if (bits1.check(i) && bits2.check(i) ){
				cout << "3->" << i << endl;
			}
		}
		cout << endl;
	}

private:
	bitset<N> bits1;
	bitset<N> bits2;
};

void test() {
	int a[] = { 10,20,4,8,40,60,10,20,30,5,5,10,7 };
	ns_bitset::bitset<100> bits;
	for (auto e : a) {
		bits.set(e);
	}
	cout << bits.count() << endl;
}

void test2() {
	int a[] = { 10,20,4,8,40,60,10,20,30,5,5,10,7,7,7,7,2,2,1,3,3,3 };
	ns_bitset::twobitset<70> bits;
	for (auto e : a) {
		bits.set(e);
	}
	bits.Debug();
}
}


void test1(){
	std::bitset<80> set;
	int a[] = { 10,20,4,8,40,60,10,20,30,5,5,10,7 };
	for (auto e : a) {
		set.set(e);
	}
	cout << set.to_string() << endl;
	cout << set.count() << endl;
}
